from typing import List
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = list()

        for first in range(n):
            if first > 0 and nums[first] == nums[first-1]:
                continue
            third = n - 1
            target = -nums[first]

            for second in range(first+1,n):
                if second>first+1 and nums[second] == nums[second-1]:
                    continue
                while second < third and nums[third] + nums[second] > target:
                    third-=1
                if second == third:
                    break
                if nums[third] +nums[second] == target:
                    ans.append([nums[first],nums[second],nums[third]])
        return ans


print(Solution().threeSum([1,0,-1,0,-2,2]))